/*
LC1012.至少有1位重复的数字
https://leetcode.cn/problems/numbers-with-repeated-digits/
难度：困难   2024.10.06  提交情况  113/130 个通过的测试用例   错误原因:超出时间限制
解题思路：暴力枚举，对每个数检查其是否有重复的数字，当数据很大时，时间复杂度很大，于是......(看题解了)

*/

/*
//暴力枚举
class Solution {
public:
    // long k = 1000000001;
    int numDupDigitsAtMostN(int n) {
        int count = n;
        if (n >= 11 && n < 22)
            return 1;

        for (int num = 1; num <= n; ++num) {
            int digits[10] = {0};
            bool flag = false;
            int t = num;
            while (t) {
                int digit = t % 10;
                if (digits[digit] == 1) {
                    flag = true;
                    break;
                }
                digits[digit] = 1;
                t /= 10;
            }
            if (!flag)
                count--;
        }
        return count;
    }
};

*/

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        // 将整数n转换为字符串，方便按位处理
        string numStr = to_string(n);
        int len = numStr.length();

        // dp[i][mask]表示考虑前i位数字，已经使用的数字集合为mask时的方案数
        // 例如，mask的二进制表示中第j位为1，表示数字j已经被使用过
        // 这里初始化dp数组，-1表示尚未计算过
        vector<vector<int>> dp(len + 1, vector<int>(1 << 10, -1));

        // 使用lambda表达式定义递归函数dfs
        // pos表示当前处理的数位位置（从左到右，从0开始计数）
        // mask是一个二进制数，表示已经使用过的数字集合
        // isLimit表示当前数位是否受到原数字n的限制（即是否只能取到n对应数位的值及以下）
        // isNum表示前面是否已经开始组成数字（例如前面是否已经取了非0数字）
        function<int(int, int, bool, bool)> dfs = [&](int pos, int mask, bool isLimit, bool isNum) -> int {
            // 如果已经处理完所有数位
            if (pos == len) {
                // 如果已经开始组成数字，则返回1，表示找到了一个满足条件的数字
                // 如果还没有开始组成数字（例如前面全是0），则返回0
                return isNum;
            }
            // 如果当前不是受限状态（isLimit为false）且已经开始组成数字（isNum为true）
            // 并且当前状态已经计算过（dp[pos][mask]!= -1），直接返回之前计算的结果
            if (!isLimit && isNum && dp[pos][mask]!= -1) return dp[pos][mask];

            int ans = 0;
            // 如果前面还没有开始组成数字
            if (!isNum) {
                // 不选择任何数字，直接跳到下一位进行处理
                ans = dfs(pos + 1, mask, false, false);
            }
            // 计算当前数位可以选择的数字范围
            int up = isLimit? numStr[pos] - '0' : 9;
            for (int i = isNum? 0 : 1; i <= up; i++) {
                // 如果数字i还没有被使用过（即mask中对应的二进制位为0）
                if ((mask & (1 << i)) == 0) {
                    // 递归处理下一位数字，更新已使用数字的集合mask
                    // 如果当前数位受限且选择了最大值（isLimit && i == up），则下一位也受限
                    ans += dfs(pos + 1, mask | (1 << i), isLimit && i == up, true);
                }
            }
            // 如果当前不是受限状态且已经开始组成数字，则保存计算结果到dp数组
            if (!isLimit && isNum) dp[pos][mask] = ans;
            return ans;
        };
        // 总的数字个数n减去不重复数字的个数（dfs(0, 0, true, false)）
        // 得到的就是有重复数字的个数
        return n - dfs(0, 0, true, false);
    }
};